package leetcode_900;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 *@author 周杨
 *AdvantageShuffle_870 类似田忌赛马的比赛 给定两个数组 问如何排列A能使A对应index元素 大于B中的 尽可能多
 *describe:对A和B排序 我们采用贪心思想 每次就给比B大一点的值  用map和队列实现 AC 82%
 *2018年11月7日 上午9:33:51
 */
public class AdvantageShuffle_870 {
	public int[] advantageCount(int[] A, int[] B) {
		int []sortA=Arrays.copyOf(A, A.length);
		int []sortB=Arrays.copyOf(B, B.length);
		Arrays.sort(sortA);//nlogn
		Arrays.sort(sortB);
		
		Queue<Integer> useless=new LinkedList<Integer>();//无用数字
		Map<Integer,Queue<Integer>>map=new HashMap<Integer,Queue<Integer>>();
		int indexA=0;
		forB:for(int i=0;i<B.length;++i) {
			while(indexA<A.length&&sortA[indexA]<=sortB[i]) {
				useless.offer(sortA[indexA++]);
			}
			if(indexA<A.length) {
				Queue<Integer> queue=map.get(sortB[i]);
				if(queue==null)//可能有重复的元素
					queue=new LinkedList<Integer>();
				queue.offer(sortA[indexA++]);
				map.put(sortB[i], queue);
			}
			else {
				break forB;//否则A中元素用完了
			}
		}
		
		for(int i=0;i<B.length;++i) {
			Queue<Integer> queue=map.get(B[i]);
			if(queue==null||queue.size()==0)//随便给一个都无所谓
				A[i]=useless.poll();
			else
				A[i]=queue.poll();
		}
		
		return A;
    }
}
